package com.example.algorithm.huawei_rongyao_29;

import java.util.Scanner;

// 请实现有重复数字的、升序的、数组的二分查找。
// 难度：简单

/**
 * 标题：二分查找 | 时间限制：1秒 | 内存限制：65536K
 * 请实现有重复数字的升序数组的二分查找。
 * 输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数(指不存在大于等于查找值的数)，则输出数组长度加一。
 * 示例1
 * 输入
 * 7,4,[1,2,4,4,5,7,9]   7表示数组长度   4表示要查找的数 输出3   这是4这个数字第一次在数组中出现的位置。计位置从1开始哦
 * 6,7,[2,4,5,5,7,8]     输出5
 *
 *
 * 有个最重要的前提是。人家给的数组，已经是有序数组了。那么，就大体以
 * 要实现有重复数字的升序数组的二分查找，可以稍作修改，当找到第一个大于等于查找值的位置时，
 * 判断其前一个位置是否小于查找值，如果小于，则说明找到了第一个大于等于查找值的位置；
 * 如果找不到，则说明数组中不存在大于等于查找值的数，输出数组长度加一。
 *
 * 以下程序实际测试多个例子，测试通过
 */
public class Q09_BinarySearchWithDuplicates {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 数组长度
        int target = scanner.nextInt(); // 查找值

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        int result = binarySearch(arr, target);
        System.out.println(result);
        scanner.close();
    }

    public static int binarySearch(int[] arr, int target) {

        // 双指针。一头一尾
        int left = 0, right = arr.length - 1;

        // left向左，right向右。直到重合之前，循环一直继续。
        while (left <= right) {
            // 这个算的是大致位于left~right中间这一段的靠中间位置的某个索引。不一定是绝对中间
            int mid = (left + right) / 2;
            //int mid = left + (right - left) / 2; 这样算也行

            // 因为是有序数组，看中间值是大于等于目标值还是小于目标值。
            if (arr[mid] >= target) {
                // 当大于等于目标值进来，并不能直接返回。因为，arr[mid]前面可能还有和arr[mid]相同的值。人家题目说了，有重复元素的升序数组。也就是，arr[mid]不一定是第一个。
                // 下面这个if条件，则可以确定，arr[mid]是第一个满足>=target的。
                if (mid == 0 || arr[mid - 1] < target) {
                    // 直接返回，结束整个方法。之所以是mid + 1，因为题目说了，位置是从1开始算起，所以要索引+1转一下。
                    return mid + 1;
                } else {
                    // right直接跳到mid-1，类似于真心话大冒险完猜数游戏。为什么是mid-1呢。
                    // 原因是上面的if已经确定了mid位置不是满足条件的，所以，mid位置已经检查过，不再划入[left~right]框定的这样一个左闭右闭区间。
                    // 注意，它之所以能称之为二分法查找，就是因为，right不是right--，而是一次就跳到right = mid - 1
                    right = mid - 1;
                }
            } else {
                // 注意，它之所以能称之为二分法查找，就是因为，left不是left++，而是一次就跳到left = mid + 1，这个步长比一次移动一个位置要大很多。
                left = mid + 1;
            }
        }
        // 按照题目要求，未找到那么就是返回数组长度加1
        return arr.length + 1;
    }
}

